Neuronske mreže
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Student: Predrag Kostić |
|
Br. indeksa: 10245 |
Rezime
|
|
|
U ovom radu, opisan je jedan stručni savetodavni sistem za
raspoređivanje rada u poštanskoj kompaniji (kompaniji za usluge
raznošenja). Taj sistem dodaje interaktivne konverzaciono-grafičke
osobine i potprogram kao podršku dispečeru u njegovim/njenim
zadacima i predlaže odgovarajuću
odluku kada naiđe novi zahtev. Eksperiment sa profesionalnim
dispečerom je takođe prikazan. |
Deo 1: Uvod
|
|
|
Prevoz je jedna od suštinskih
delatnosti unutar mnogih organizacija. Roba i usluge se distribuiraju mušterijama preko službe
prevoza, pa ova delatnost mora biti efikasno izvršena. U suštini, efikasnost
utiče na smanjenje troškova operacija i povećanje kvaliteta usluge.
Gledano sa strane dispečera, sposobnost da se nađe dobar kompromis
između ova dva suprotna zahteva je veoma važno pitanje. |
|
|
|
Brojni primeri distribuiranja u
“realnom vremenu” mogu se naći u praksi, kao što su ambulantne ili
policijske usluge, usluge slanja paketa ili kućne dostave, transport
hendikepiranih, kao i mnoge druge. U ovom delu, mi smo se fokusirali na
specifičnu oblast: kompaniju za
poštanske usluge iz Montreala. Ovde, pisma moraju biti sakupljena i
dostavljena sa jednog mesta na drugo u uličnoj mreži, tako da zadovolji
prioritete korisnika usluga. Za
prioritete su obično navedeni rokovi maksimalnog vremena
preuzimanja i dostavljanja ( npr. pismo mora biti preuzeto za vreme od 30min,
i dostavljeno u vremenu od 90min.). |
Deo 1: Uvod
|
|
|
Da bi dosledno zadovoljio zahteve na
najbolji mogući način uz pomoć omogućenog voznog parka,
dispečer mora obratiti pažnju na mnogo različitih faktora, kao što
su: |
|
|
|
Trenutna pozicija svakog od
vozača, |
|
Planiran pravac kretanja i raspored
svakog vozača (za prethodno dodeljen zahtev), |
|
Lokacije za mesto preuzimanja i mesto
dostave novog zahteva, |
|
Distance i vreme putovanja između
tačaka preuzimanja i dostave, |
|
Karakteristike osnovne transportne
mreže. |
|
|
Deo 1: Uvod
|
|
|
Dakle, dispečer je ključni
elemenat u kompanijama za poštanske
usluge. Nažalost, nije lako pronaći dobre dispečere, zbog
specifičnih veština koje su neophodne za adekvatno izvršavanje zadatka.
Štaviše, potrebno je dosta vremena za obuku dispečera, a njihova
profesionalna karijera obično traje samo nekoliko godina zbog visokog
nivoa napetosti usled potrebe za pravilnim reagovanjem, kao i zbog brzog i
dinamičnog razvitka sredine. |
|
Prema tome, razvoj stručnog
sistema sposobnog za pomoć dispečerima vozila je od velike
ekonomske važnosti. Međutim, naše sopstveno iskustvo je pokazalo da je
to veoma teško, ako ne i nemoguće da se formalizuje znanje dispečera
(npr. preko pravila odluke, semantičkih mreža itd.). Stoga, naš sistem
je baziran na tehnikama učenja automata, na detaljnom učenju kroz
primere, gde su primeri odluka sakupljeni i analizirani od strane sistema i
prilagođeni kao proces dispečerovih odluka. Očigledno, mnogo
je lakše uzeti primere odlučivanja dispečera nego izvući jasna
pravila odlučivanja kod njih. |
|
Potprogram učenja unutar sistema
je baziran na modelu neuronskih mreža. Nakon faze obuke sa stručnjakom,
sistem moze predlagati dispečeru vozače koji bi mogli zadovoljiti
novopridošle zahteve. Naravno, dispečer ima konačnu odluku i
slobodan je da prihvati ili odbije predloge sistema. |
Deo 1: Uvod
|
|
|
Potprogram učenja je ugrađen
u granicama konverzacije sa ciljem da pomaže dispečeru u njegovim
zadacima. U ovom delu, razmatrani su sledeći problemi: |
|
Lokalizacija novih zahteva unutar mreže
ulica |
|
Procena vremena putovanja i razdaljine |
|
Rezultati dodele zahteva određenom
vozaču |
|
Definisanje kriterijuma učinka kod
vozača, kao što su mogućnost zaobilaska, vreme preuzimanja, vreme
dostavljanja itd. |
|
Dinamika potprograma učenja |
|
Za potrebe testa, prototip je
korišćen kao simulator posebnih događaja, i primenjen je na
prethodno sakupljena dokumenta i zahteve. Ovi podaci potiču iz poštanske
kompanije iz Montreala. |
|
U sledećem, drugom delu,
upoznaćemo se sa problemima dodele. Zatim, deo 3 opisuje sistem dodele i
njegove razne delove. Potprogram učenja je predstavljen u delu 4, i
razni eksperimenti sa profesionalnim dispečerom opisani su u delu 5. |
Deo 2: Problemi dodele
|
|
|
Posmatrajmo sledeći problem.
Kompanija za poštanske usluge primila je poziv za preuzimanje i dostavu
prioritetnog pisma u gradskom području. Svaki korisnik jasno definiše
mesto preuzimanja i dostave, i maksimalno vreme usluge u svakoj od tačaka.
Obzirom da većina korisnika traži brzu uslugu, putanja i raspored moraju
biti određeni u realnom vremenu. U tako zahtevno osetljivom sistemu,
sistem posmatra kada novi korisnik pozove kancelariju dispečera.U to
vreme, pisma nekih ranijih korisnika su već dostavljena i, prema tome,
više se ne razmatraju. Ostali korisnici su dodeljeni vozačima, i njihova
pisma ili treba da budu preuzeta, ili su na putu da budu dostavljena. Pored
toga,u to vreme, put i raspored za svakog vozača je poznat. Problem je
odlučiti kom vozaču dodeliti zadatak, i koji put i raspored mu
postaviti. U rešavanju ovog problema, dispečer mora pronaći
kompromisno rešenje između dve stvari: umanjenja troškova i zadovoljenja
potrebe korisnika. |
|
Dinamički problemi kao što je
ovaj i dalje su ostavljeni ljudima-dispečerima. Međutim, nekoliko
algoritama je predloženo u literaturi, u pojedinim algoritmima na osnovu
stečenog znanja koje su razvili Wilson i Covin ’79, za “dial-a-ride”
transportni sistem u Ročesteru, NY. Dinamički programiran algoritam
za pojedinačno vozilo je takođe, opisao Psaraftis ’80. |
Deo 2: Problemi dodele
|
|
|
Ipak, pristup ovde pokazan je dosta
drugačiji. Razvijen je sistem sposoban za simulaciju procesa
odlučivanja dispečera eksperta, nakon faze obuke sa ovakvim
ekspertom. Zato sistem može lako biti prilagođen drugim uslovima dodele.
Pošto se procedura odlučivanja može dosta menjati od jedne organizacije
do druge, nosivost sistema je veoma važan faktor ovde. |
|
|
Deo 3: potprogram dodele
|
|
|
Sistem uključuje i potprogram
dodele za asistiranje dispečeru pri njegovim zadacima, kao i potprogram
učenja za predloge odluka. U ovom delu, mi ćemo se ograničiti
na razne delove potprograma dodele. Potprogram učenja biće
razmatran u sledećoj oblasti. |
|
Slika 1 opisuje tok kontrole
između 5 komponenti potprograma dodele. Ove komponente biće sada
opisane redom. |
3.1. Lokalizacija zahteva
|
|
|
Unutrašnji prikaz cele mreže ulica u
Montrealu nalazi se u sistemu. Svaki čvor u ovoj mreži predstavlja
raskrsnicu ulica a svaka veza je deo ulice između dve raskrsnice.
Unutrašnji prikaz mreže uključuje |
|
20 000 čvorova, 30 000 veza i 6
000 ulica. Zadatak potprograma za lokalizaciju je da transformiše adresu
preuzimanja i dostave u element na strukturi mreže (npr. Čvor ili vezu).
Adresa može biti zadata na četiri jasno određena načina: |
|
Građanskom adresom, imenovanjem,
građanskim brojem i imenom ulice, |
|
Poštanskim kodom, |
|
Imenom (npr. Montrealski Univerzitet), |
|
Raskrsnicom ulica (npr. ugao ulice
Saint-Laurent i Sherbrooke) |
|
Kada je adresa locirana na mreži,
njene koordinate su pronađene i razdaljina i vreme prenosa na drugu
adresu mogu biti procenjene. |
3.2. Procena razdaljine
|
|
|
Ovde je problem proceniti dužinu
najkraćeg puta između dve adrese u mreži (nadalje, to će se
odnositi na “tačnu razdaljinu”). Dva alternativna pristupa će biti
razmatrana ovde: |
|
Proračunavanje tačne
razdaljine između svih parova adresa u mreži, i njihovo skladištenje u
tabeli rastojanja za naredno korišćenje. |
|
Proračunavanje tačne
razdaljine između dve adrese svaki put kada je to potrebno. |
|
Prvi pristup nije realan za velike
mreže, iz razloga što bi tada tabela rastojanja bila prevelika da bi bila
postavljena u glavnu memoriju ( primetimo da N adresa generišu O(N2)
parovnih rastojanja). Sa druge strane izračunavanje tačne
razdaljine “po zahtevu” je nefunkcionalno zbog mnogo vremena potrošenog na
računanje. Procena najkraće putanje je skupa jer dve tačke
mogu biti dosta udaljene, i specifične potrebe moraju biti
uračunate pri proceni, kao što su jednosmerne ulice i zastoji pri
skretanju u levo. |
|
Kako bi dosledno omogućili
kraće vreme izračunavanja, uzeli smo međupristup tako što smo
podelili mrežu ulica na 502 zone veličine kvadratnog kilometra. Unutar
svake zone, najvažnija raskrsnica je definisana kao “centar” zone. Tačne
razdaljine su izračunate između svakog para centara, i postavljene
su u tabelu rastojanja. Veličina tabele je oko 1MB, i može biti
postavljena u glavnu memoriju |
3.2. Procena razdaljine
|
|
|
Da bi odredili tačnu razdaljinu
između lokacije 1 u zoni 1 i lokacije 2 u zoni 2 , korišćena je
sledeća relacija: |
|
|
|
|
|
|
|
Bez obzira na odnos između samih
položaja, očekivano je da odnos između tačnog i Menhetn
rastojanja između centra u zoni 1 i centra u zoni 2 bude približno
jednak odnosu između tačnog i Menhetn rastojanja između lokacije
1 i lokacije 2. Obzirom da je razdaljina između centara u zoni 1 i zoni
2 poznata, i Menhetn razdaljina je laka za izračunavanje, mi imamo
način za brzi proračun tačne razdaljine između lokacije 1
i lokacije 2. Detaljnije, ako postoji smetnja između 2 zone (npr.
industrijsko postrojenje), odnos razdaljina između centara zone 1 i zone
2, biće veći i dovešće , preko odnosa, do veće procene
između tačnog rastojanja između lokacije 1 i lokacije 2. Ovakav
pristup se pokazao kao veoma brz i dosta precizan. U slučajevima kada su
obe lokacije u istoj zoni, koristi se samo Menhetn rastojanje. |
3.2. Procena razdaljine
|
|
|
Slika 2 pokazuje razliku između
tačne i Menhetn razdaljine u uličnoj mreži. Sivi pravougaonici
predstavljaju kuće ili blokove kuća, a beli delovi između
sivih pravougaonika predstavljaju ulice u mreži. Kao što možemo videti u
primeru, tačno rastojanje je veće od Menhetn rastojanja, jer pri
tačnom računanju moraju se pratiti ulice u mreži, da bi se izbegle
prepreke. |
3.3. Procena vremena
prenosa
|
|
|
Kada saznamo rastojanje između dve
tačke, vreme prenosa možemo izvesti na osnovu prosečne brzine
kretanja vozila. U sistemu, brzina je funkcija razdaljine. Zapazimo da kada
su dve tačke dosta udaljene, vozač obično koristi veće
ulice, i prosečna brzina se poveća. |
|
Funkcija brzine uključuje šest
parametara: |
|
VITMIN, minimalnu brzinu, |
|
VITMOY, prosečnu brzinu, |
|
VITMAX, maksimalnu brzinu |
|
d1,d2 i d3, tri tačke duž ose
razdaljine za definisanje funkcije brzine. |
|
Sa ovim parametrima, po delovima
linearna funkcija brzine, kao što je prikazano na slici ispod, je definisana: |
3.3. Procena vremena
prenosa
|
|
|
Za zadato rastojanje d izmedju dve
tačke, prosečna brzina je zatim brzo određena i vreme prenosa
je procenjeno. |
|
Dodatni parametri su takođe
dostupni modelu kao spoljašni faktori koji deluju na prosečnu brzinu,
kao što su: |
|
Meteorološki uslovi. Vreme prenosa može
biti pomnoženo sa koeficijentom
između 1 i 5 koji označavaju teža stanja na putevima ( jaku kišu,
sneg), |
|
Produktivnost vozača. Vreme
prenosa može biti podeljeno koeficijentom između 1 i 2, u zavisnosti od
vozača. Koeficijenat 1 je za normalnog, a koeficijenat 2 je za dva puta
bržeg od normalnog. |
|
Gužva u saobraćaju. Tokom špica,
ima mnogo više gužve u saobraćaju. Vreme prenosa može biti pomnoženo
koeficijentom od 1 do 2 da bi se uzeo u obzir i faktor gužve. |
|
Na osnovu svega toga, vreme prenosa se
može prikazati kao: |
3.4. Ubacivanje novih
zahteva
|
|
|
Zadatak dispečera je da dodeli
novi zahtev nekom od raspoloživih vozača. Koristeći tehnike opisane
u poglavljima 3.2. i 3.3. za procenu rastojanja i vremena prenosa, sistem
može pomagati dispečeru pri oceni rezultata dodavanja novog zahteva u
neku od postojećih trasa. Na osnovu ovih informacija, mnogo je lakše
dispečeru da donese dobre odluke. |
|
Očigledno, mnoge dodatne
tačke su izvodljive u svakoj trasi, iz razloga što najveći deo
vremena usluge određenog od strane korisnika nije teško prilagodljiv,
već normalno predpostavljen. Jedini uslov je da tački dostave mora
predhoditi tačka preuzimanja. Prema tome, usvojena ubačena
tačka je odabrana u svakoj trasi tako da minimizuje obilaženje (u
vremenu) plus dodatna kazna za naknadno zadržavanje uneto u trasu sa novim
zahtevom. Naime, ako je tačka preuzimanja +j zahteva j uneta između servisnih
tačaka i i k, tačka dostavljanja –j zahteva j je ubačena
između l i m, i je vreme prenosa između i i j,
troškovi dodavanja bi bili smanjeni na: |
3.4. Ubacivanje novih
zahteva
|
|
|
U ovoj formuli, predstavljaju novo
vreme usluge, staro vreme usluge i maksimalno vreme usluge, respektivno. Prve
dve komponente u formuli troškova predstavljaju zaobilazno vreme za nova
mesta preuzimanja i dostave, dok je treći termin suma naknadnog
kašnjenja preko +j,-j i svih ostalih servisnih tačaka koje nailaze posle
+j u trasi (većina promenljivih od
+j i –j su postavljene na 0). Minimizacija
obilaznog vremena je heuristicki način smanjenja sume poremećaja u
trenutnoj trasi. Sa druge strane, jedna promena obilaznog vremena može
izazvati mnogo zakasnelih usluga u jednoj trasi i nekoliko u drugim trasama,
u zavisnosti od razlike između proračunatog i maksimalnog vremena
usluge. Ovo je u obračunu uzeto kaozadnja stavka u formuli troškova. |
|
Slika 4 ilustruje proces dodavanja. Na
slici, +j i –j predstavljaju respektivno tačke preuzimanja i dostave
zahteva j, a X predstavlja zadnju tačku usluge vozača u trenutnom
vremenu. Dakle, vozač je već uslužio tačku X, i krenuo je
prema tački preuzimanja zahteva 1. U to vreme, korisnik 3 poziva servis.
Dodato mesto sa minimalnim troškovima za ovaj novi zahtev je pokazano na
slici. Sa ovim novim zahtevom, planirana vremena usluge u +2, -2 i -1 su
odložena, i ubačena nova vremena usluge u sistem. |
3.4. Ubacivanje novih
zahteva
3.5. Odabir vozača
|
|
|
Prezentacija različitih
alternativnih trasa je omogućena da pomogne dispečeru da odabere
odgovarajućeg vozača. Detaljnije, sistem ističe devet
karakteristika ili osobina da bi opisao trasu: |
|
D.E.
Zaobilazno vreme usled novog zahteva |
|
P.T. Vreme preuzimanja novog zahteva |
|
D.T. Vreme dostave novog zahteva |
|
Avg. P Lat. Prosečno vreme
kašnjenja na mesto preuzimanja usled obaveze zbog umetanja novog zahteva |
|
Avg. D Lat. Prosečno vreme
kašnjenja na mesto dostave usled obaveze zbog umetanja novog zahteva |
|
#P Lat. Broj naknadnih zakasnelih
usluga na mestima preuzimanja, usled obaveze zbog umetanja novog zahteva |
|
#D Lat. Broj naknadnih zakasnelih
usluga na mestima dostave, usled obaveze zbog umetanja novog zahteva |
|
#Req. Broj zahteva na trasi |
|
Et. Tr. Odnos praznog vremena prenosa i
ukupnog vremena prenosa. Vozilo ide prazno kada se krece prema tački
preuzimanja, i tada nema pošte u vozilu. |
3.5. Odabir vozača
|
|
|
Ekran 1, koji vidimo na slici 5,
rangira vozače ili trase prema visini karakteristika (primetimo da NN
predstavlja produkt neuronskih mreža, kao što će biti opisano u
sledećem delu). Ova slika prikazuje da je vozač Potvin najbolji vozač
za usluživanje novih zahteva ako uzmemo u obzir zaobilazne karakteristike DE,
sa vremenom obilaska od 2.1 min. Vozač Vincent je drugi sa vremenom
zaobilaska od 3.3 min., itd. Mali prozori su klizni, pa je moguće videti
mesto na rang listi bilo kog vozača u vezi sa bilo kojom
karakteristikom. |
3.5. Odabir vozača
|
|
|
Ekran 2, koji vidimo na slici 6, je
alternativni ekran. On pokazuje rangiranje svih vozača odjednom. Na
primer, vozač Rioux je peti prema vremenu obilaska DE, prvi po vremenu
preuzimanja PT, prvi po vremenu dostave DT, itd. Da napomenemo da slike 5 i 6
predstavljaju prave ekrane. |
|
|
3.5. Odabir vozača
|
|
|
Gledajući ove brojeve,
dispečer može odabrati određenog vozača, klikćući
mišem na liniju sa vozačevim imenom. Po selektovanju, prikazuje se cela
trasa, sa specijalnim zasenčanjem za mesta preuzimanja i dostave novog
zahteva.(videti sliku 7). Na trasi je prikazano planirano i maksimalno vreme
usluge za obe adrese, kao i simbol “>” koji se pojavi između dve
vrednosti kada se detektuje neko kašnjenje. |
|
Dispečer mora potvrditi trasu.
Ako mu se ne sviđa trasa, omogućene su mu tri mogućnosti.
Prvo, on može pomeriti tačke preuzimanja i dostave na druge lokacije
unutar trase, kako bi našao bolje mesto dodavanja. Kada su tačke pomerene
na novu lokaciju, planirano vreme usluge u svakoj tački duž trase se
automatski koriguje. Dispečer može zatražiti korekciju rang liste na
ekranu 1 i ekranu 2, baziranu na novom mestu dodavanja. |
|
Druga mogućnost je da poništi
selekciju, i vrati se na ekrane 1 i 2 kako bi odabrao novog vozača. Kada
dispečer potvrdi odabir vozača, trasa se trajno menja kako bi
uključila novi zahtev. |
|
Treća mogućnost je
ostavljanje zahteva na listu “neodlučenih” zahteva, i sačekati
druge zahteve da dođu pre konačne odlike. |
3.5. Odabir vozača
Deo 4: potprogram
učenja
|
|
|
Potprogram učenja ima za cilj
predlaganje “dobrih” vozača za usluživanje novih zahteva. Bez ovog
potprograma, sistem bi imao neaktivnu ulogu u pomaganju dispečeru. “Back
propagation” neuronska mreža predstavlja srž potprograma učenja. (za
totalni opis ovog modela pogledati [Rumelhart i McClelland 86]). |
|
“Backpropagation” mreža je
tipično sastavljena od tri sloja prostih procesorskih jedinica, nazvanih
ulazni sloj, skriveni sloj i izlazni sloj. Svaki sloj je u potpunosti povezan
sa sledećim slojem težinskim vezama. Ulazne vrednosti su prdviđene
za ulazni sloj, i ove vrednosti se prostiru duž težinskih veza do skrivenog
sloja gde se obrađuju. Nakon toga, ponavlja se isti postupak između
skrivenog i izlaznog sloja. Konačne vrednosti smeštene su u izlaznom
sloju, i odgovaraju poslednjoj karakteristici (ili izlazu) mreže. |
|
Tokom prostiranja, skrivene i izlazne
jedinice transformišu svoje ulaze putem dobro poznate sigmoidalne aktivacione
funkcije [Rumelhart i McClelland 86]: |
Deo 4: potprogram
učenja
|
|
|
Ne vredi ništa ako je aktivaciona
vrednost svake jedinice na intervalu [0,1] posle procesiranja ulaza od strane
sigmoida. Praktično, aktivaciona vrednost izlaznih jedinica je vrednost
izmedju 0 i 1, i ona je odgovor neuronske mreže na trenutni ulazni vektor. |
|
Moć “backpropagation” mreža ogleda
se u njihovim sposobnostima da se prilagode težini svojih veza kako bi
naučili specifične zadatke. Algoritam učenja koristi željeni
izlazni vektor ili odluke donete od strane eksperta za svaki ulazni vektor (opisujući
problematičnu situaciju). Kada trenutni izlaz ne odgovara željenom
izlazu, greška se koristi da prilagodi težinu veza između slojeva. |
|
Mnogi parovi (ulaz,željeni izlaz) su
određeni od strane mreže za svrhe vežbanja. Ovi parovi se obrađuju
jedan po jedan od strane mreže da postepeno prilagode težine dok se ne pojavi
konvergencija. Obično, beznačajno mala greška se podesi između
trenutnog i željenog izlaza kako bi proverili ispravnost mreže, i vežba
prestaje kada se pokazatelj ove greške stabilizuje. |
|
Iz prethodnog obrazloženja, jasno je da
podatak mora prvo biti kodiran u formu ulaznog vektora za neuronsku mrežu. U
našem modelu, svaki ulazni vektor kodira opis situacije raspodele za svakog
vozača pojedinačno. Ako je n broj vozača, n ulaznih vektora je
prema tome kreirano za svaki novi zahtev. Ulazni vektor odabranog vozača
je dobijen je na osnovu devet kriterijuma ili karakteristika opisanih u delu 3.5 (zaobilazno vreme, vreme
preuzimanja, vreme dostave, itd.). |
Deo 4: potprogram
učenja
|
|
|
Prema tome, ulazni vektor
vozača j za novi zahtev i je: |
|
|
|
|
|
gde je p-ta karakteristika vozača j za
zahtev i , a m je broj karakteristika (u ovom slucaju m=9). |
|
Veoma je važno da primetimo da svaka
vrednost karakteristike nosi mali
značaj u sebi. Na primer, zaobilazno vreme od 15 min. za vozača
može biti dobro ili loše, u zavisnosti od ostalih vozača. Prema tome,
informacija je prosleđena za sve vozače. Ako mi želimo obezbediti
“backpropagation” neuronsku mrežu sa opisom koji uključuje samo po
jednog vozača u trenutku (po redu kako bi smanjilo veličinu ulaznih
vektora), potrebneje da vrednosti karakteristika budu transformisane u nove vrednosti
koje mogu biti protumačene bez obraćanja pažnje na ostale
vozače. |
Deo 4: potprogram
učenja
|
|
|
Mi tako prilagođavamo dve naredne
transformacije kako bi postigli ovaj cilj: |
|
Prevod. Zadati novi zahtev i i vrednost
karakteristike , sledeća
transformacija je prva prilagođena: |
|
|
|
|
|
gde je n broj vozača i m broj
karakteristika. Za bilo koju karakteristiku p, za najboljeg vozača j*, i
preostale vrednosti odgovaraju razlici od najbolje
vrednosti. Geometrički, ova transformacija prevodi ulazni vektor svakog
vozača u odnosu na vektor |
Deo 4: potprogram
učenja
|
|
|
Normalizacija. Gornje vrednosti su
normalizovane između 0 i 1, na sledeći način: |
Deo 4: potprogram
učenja
|
|
|
Slika 8 pokazuje tri sloja neuronske mreže baziranih na kodiranju
podataka za m=3 karakteristike. Za svaku normalizovanu vrednost
karakteristike postoji ulazna jedinica. Takođe postoje
tri skrivene jedinice povezane sa svakom ulaznom jedinicom. Zadnji sloj
sastoji se od jedinstvene izlazne jedinice sa ciljem da uslovi višestruke procene
kvaliteta vozača. Primetimo takođe da je ulazni sloj direktno
povezan za skriveni sloj i za izlazni sloj. Direktna veza između ulaznih
i izlaznih jedinica obično nije prisutna u standardnoj “backpropagation”
mreži, ali bolji rezultati su zabeleženi sa ovim modelom. |
|
|
Deo 4: potprogram
učenja
|
|
|
Eksperiment opisan u poslednjem delu
odnosi se na ovu mrežnu strukturu. Ipak, devet ulaznih jedinica je
upotrebljeno, t.j. jedna ulazna jedinica za svaku vrednost karakteristike
(pogledati deo 3.5) |
|
Neuronska mreža je trenirana sa
klasičnim “backpropagation” algoritmom [Rumelhart i McClelland 86].
Svaka odluka eksperta, koji je ili odabrao ili odbio vozača povezanog sa
trenutnim ulaznim vektorom, iskorišćena je da poboljša tačnost
mrežnog odgovora, i prilagodi težinu veza u slučaju greške. Kao što je
pomenuto pre, greška je bazirana na razlici između odgovora mreže i
željenog odabira. Ovde je željeni odabir postavljen na 1 za vozača
odabranog od strane dispečera, a na 0 za drugačiji slučaj. |
|
Kada je jednom uvežbana, neuronska
mreža može biti prilagođena novim primerima: odgovor koji je blizu 1
znači da vozač koji je povezan sa trenutnim ulaznim vektorom je
dosta pogodan za usluživanje novog zahteva, dok vrednost blizu 0 znači
suprotno. Primetimo da se izlazi neuronske mreže pojavljuju na prozoru 1
unutar kliznog ekrana NN (videti sliku 5). |
Deo 5: Simulator
|
|
|
Da bi sakupio primere odluka,
potprogram dodeljivanja je sada ugrađen u poseban simulator
događaja. Ceo sistem je sproveden u Turbo-Paskalu i pušten na IBM PS/2
mikroračunaru. |
|
Dva tipa događaja se mogu javiti
tokom simulacije: Događaj zahteva kada novi zahtev naiđe i događaj
vozača kada se vozač javi sa mesta preuzimanja ili mesta dostave.
Događaji zahteva se čitaju sa ulaznih dokumenata, a događaji
vozača se generišu kada su zahtevi dodeljeni. Tokom simulacije, sat se
pomerao u odvojenim vremenskim koracima zasnovanim na vremenski najbližem
sledećem događaju. Kada je trenutni događaj događaj zahteva, simulator se
zaustavlja da bi dozvolio ekspertu da dodeli zahtev (videti deo 3). |
Deo 5: Simulator
|
|
|
Ekran simulacije pokazan je na slici
9. Mali gornji prozor pokazuje trenutni događaj, koji je ili
događaj zahteva ili događaj vozača (npr. događaj
zahteva). Veliki prozor na sredini ekrana pokazuje trenutno stanje svih
vozača. Ako je vozač slobodan, njegova trenutna pozicija je
označena. U suprotnom, pokazane
su polazna i odredišna tačka vozača. Trenutno vreme usluge
na polaznoj tački i očekivano vreme usluge na odredišnoj tački
su takođe prikazani, kao i maksimalno vreme usluge u svakoj tački.
Primetimo da je očekivano vreme usluge na odredišnoj tački uzeto od
strane simulatora da bi odredilo sledeći događaj, vremenski najbliži.
U trenutnom izvršavanju, očekivano i trenutno vreme usluge su isti, zato
što simulator ne generiše još uvek neki neočekivani događaj (kao
što su neočekivana kašnjenja, kvar na vozilima, itd.). Konačno,
prozor pri dnu ekrana se koristi za nerešene zahteve. |
Deo 5: Simulator
|
|
|
Sadašnji sistem dodeljivanja može biti
iskorišćen na tri različita načina, kao što prikazuje slika
10. |
|
Sakupljanje podataka. Ovde, odluke
dispečera se sakupljaju tokom simulacije i skladište u dokument sa
primerima vežbanja i testiranja da bi se kasnije iskoristili od strane
neuronske mreže. Ovaj dokument sadrži vozače izabrane od strane
dispečera za svaki zahtev, kao i opis situacije dodeljivanja za svakog
vozača ( na osnovu karakteristika iz dela 3.5.). |
|
Vežba/Testiranje neuronske mreže. Ovaj
način korišćenja je uzet za treniranje ili testiranje neuronske
mreže na osnovu dokumenta sa primerima kreiranog u “sakupljanju podataka”. U
delu treniranja, primeri su iskorišććni da prilagode težine veza. U
delu testiranja, karakteristike mreže se procenjuju poređenjem njenih
odluka ( sa trenutnom grupom težina) sa odlukama dispečera. Kao što je
prikazano na slici 10, ovaj deo uključuje samo potprogram učenja. |
|
Predlog vozača. Ovde korisnik može
pogledati predloge (prethodno uvežbane) neuronske mreže da bi dodelio novi
dokument ili zahtev. Ako je tako poželjeno, težina veza neuronske mreže je
prilagodjena kada se konačna odluka razlikuje od vrha rangiranih
predloga neuronske mreže. |
Deo 5: Simulator
Deo 6: Rezultati
eksperimenta
|
|
|
Sa namerom da procenimo ispravnost
potprograma učenja, izvršili smo eksperiment sa profesionalnim
dispečerom na grupi zahteva prikupljenoj u radnom danu kompanije za
poštanske usluge iz Montreala. Ukupno 140 zahteva je sakupljeno od 9.00h do
15.00h, i 12 vozača je bilo iskorišćeno za usluživanje ovih
zahteva. |
|
S’obzirom na kvalitet usluga, uzete su
sledeće pretpostavke: |
|
Maksimalno vreme preuzimanja zahteva j
je postavljeno na vreme zahteva korisnika j plus 30 minuta (gde vreme zahteva
korisnika j predstavlja vreme poziva) |
|
Maksimalno vreme dostave zahteva j je
postavljeno na vreme zahteva korisnika j plus 90 minuta. |
|
Iz toga, kašnjenja na tačkama
preuzimanja i dostave +j i –j su računata na sledeći način: |
Deo 6: Rezultati
eksperimenta
|
|
|
Prema tome, dispečer je podelio
140 zahteva redom na 12 vozača. Na kraju, 140*12=1680 ulaznih vektora je
bilo omogućeno za uvežbavanje i testiranje neuronske mreže. Mi smo
iskoristili 90 zahteva za uvežbavanje mreže i 50 zahteva za testiranje.
Karakteristike mreže na grupi za testiranje su procenjene upoređivanjem,
za svaki zahtev, rangiranja od strane neuronske mreže i vozača izabranog
od strane dispečera. Ovo rangiranje je određeno sortiranjem izlaza
neuronske mreže za sve vozače u opadajućem redu. |
|
Na primer, pretpostavimo da su
sortirani izlazi neuronske mreže za n=5 vozača: |
|
Vozač 1: 0.9 |
|
Vozač 4: 0.8 |
|
Vozač 3: 0.6 |
|
Vozač 5: 0.4 |
|
Vozač 2: 0.1 |
|
Ako je izabran vozač 4 od strane
dispečera, rangiranje dato od neuronske mreže za ovaj izbor je 2. |
Deo 6: Rezultati
eksperimenta
|
|
|
Ova rangiranja su prikazana u tabeli 1
za 50 zahteva u grupi za testiranje. Težine veza neuronske mreže se dobiju
posle 100.000 težinskih korigovanja ili ponavljanja učenja na grupi
zahteva za učenje (počinjuci sa slučajnim težinama).
Učenje mreže na 486 IBM PS/2
trajalo je 24 sata. |
Deo 6: Rezultati
eksperimenta
|
|
|
Tabela 1 prikazuje da je 80%
vozača odabrano od strane eksperta rangirano kao prvi, drugi ili
treći od strane neuronske mreže (t.j. 40 odluka od 50). Štaviše, 94%
vozača je rangirano kao prvi, drugi, treći ili četvrti od
strane neuronske mreže. Ove cifre pokazuju da neuronska mreža može biti veoma
korisna da odstrani vozače, i usmeri pažnju dispečera na
najinteresantnije mogućnosti. |
|
Nebitno je da li je dosta podjednako
dobrih (podjednako loših) mogućnosti omogućeno ako se ne podudaraju
izbori neuronske mreže i eksperta. U ovakvim situacijama, mreža uvek odabere
prihvatljivog vozaća (t.j. nema “budalastih” izbora). |
Deo 6: Rezultati
eksperimenta
|
|
|
Takođe smo iskoristili
naučenu mrežu da dodeljuje celu grupu zahteva jedan po jedan. Tada smo
upoređivali trase neuronske mreže i trase dispečera, prema
sledećim merama učinka: |
|
Produktivnost. Mera produktivnosti
upoređuje ukupno vreme putovanja na trasi sa sumom direktnih vremena
putovanja između tačaka preuzimanja i dostave za svaki zahtev na
trasi. Kasniji slučajevi odgovaraju situaciji kada je svaki zahtev
uslužen od strane posebnog vozila (kao taxi služba). |
|
U formuli ispod, produktivnost trase r je
definisana kao odnos ove dve vrednosti. Primetimo da je u brojiocu suma
direktnih vremena putovanja svih zahteva u u trasi. |
|
|
|
|
|
|
|
|
|
Odnos praznog vremena putovanja i
ukupnog vremena putovanja |
|
Suma kašnjenja na mestima preuzimanja
(u minutima) |
|
Suma kašnjenja na mestima dostave (u
minutima) |
Deo 6: Rezultati
eksperimenta
|
|
|
Kriva ispod pokazuje razvoj ovih
vrednosti sa dodelom zahteva od strane mreže ili od strane eksperta. X-osa
predstavlja broj odluka dodele, a Y-osa mere učinka pod analizom.
Vrednosti su snimane posle svake sekvence od deset odluka i sabrane su. Na primer,
mera produktivnosti kod 30-e odluke dodele je prosek uzet od svih trasa,
posle dodavanja 30-og zahteva. U ovom procesu, svi dodeljeni zahtevi
doprinose proseku. |
|
Na svakoj slici, krive neuronske mreže
su one sa malim krugovima, a krive dispečera su one sa malim
kvadratićima. Kao što možemo videti, neuronska mreža pokazala se dobro u
odnosu na prazno vreme putovanja, produktivnost, i kašnjenja na mesta preuzimanja.
Ipak, ekspert je bolji u odnosu na kašnjenja na mesta dostave.
Najčešće, trase neuronske mreže imaju dve zakasnele usluge na
mestima preuzimanja (oko 5 minuta u svakom mestu), i tri zakasnele usluge na
mestima dostave (oko deset minuta nu svakom mestu). Sa druge strane, trase
dispečera imaju tri zakasnele usluge na mestima preuzimanja, i samo
jednu zakasnelu uslugu na mestima dostave. |
|
Prema tome, neuronska mreža se pokazala
dosta dobro prema merama učinka. Čak iako se nije pokazala kao
dispečer u odnosu na ukupna kašnjenja na mestima dostave, vrednosti
neuronske mreže su veoma impresivne. Takođe, dispečer je pritisnut
zbog važnosti dolaska u pravo vreme na mesto preuzimanja (korisnici ne vole
da vide pismo na svome stolu dugo vremena po pozivu postanske kompanije!).
Interesantno je da je neuronska mreža uradila veoma dobar posao u tom
pogledu. |
Deo 6: Rezultati
eksperimenta
Deo 7: Zaključak
|
|
|
Sistem predstavljen u ovom radu je
razvijen da predstavi upotrebljivost tehnologije neuronskih mreža u zadacima
dodele vozila. Međutim, sistemu su potrebne dodatne osobine kako bi bio
koristan u realnom ambijentu. Na primer, trenutna pozicija svakog vozača
treba biti lakše korigovana (idealno bi bilo preko ‘on-board’ kompjutera), i
revizija trasa trebala bi biti omogućena u slučajevima dugog
neočekivanog kašnjenja. |
|
U odnosu na potprogram učenja,
faza vežbanja uzima dosta vremena, ali to nije toliko bitno, zato što to može
biti urađeno sa unapred sakupljenim primerima odluka (kao što smo mi
uradili u našim eksperimentima). Kada se nauči, mreža reaguje veoma
brzo, i može biti upotrebljena u realnoj sredini. |
|
Konačno, ne vredi ništa ako
potprogram učenja uradi dobro, ako nije u saglasnosti sa procenjenim vremenom putovanja i
razdaljinama. Dispečer je uvideo da su vremena putovanja veoma realna u
većini slučajeva, ali je očigledno da ove procene
predstavljaju dodatni hendikep za potprogram učenja. |